package src.CodeTop;

/**
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *  
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 * 示例 2：
 *
 *
 * 输入：head = [1,2]
 * 输出：[2,1]
 * 示例 3：
 *
 * 输入：head = []
 * 输出：[]
 */

public class _206ReverseLinkedList {
    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 2, 3, 4, 5};
        int[] arr2 = new int[]{1, 2};
        ListNode head = TestListNode.generateLinkedList(arr1.length, arr1);
        ListNode target = reverseList(head);
        TestListNode.showLinkedList(target);
    }

    /**
     * 虚头迭代法
     * @param head 头结点
     * @return 翻转后的头结点
     */
    public static ListNode reverseList1(ListNode head) {
        // 校验合法性
        if (head == null) {
            return null;
        }
        // 创建一个新链表的头结点
        ListNode reversedHead = new ListNode(0);
        // 定义辅助指针用来遍历原链表
        ListNode cur = head;
        // 定义一个指针用来防止链表断裂，也即保存辅助指针所在的下一个结点
        ListNode next = null;
        // 遍历原链表
        while (cur != null) {
            // 先将next指针指向cur的下一个结点
            next = cur.next;
            // 将当前指针连接到新的链表的头部
            cur.next = reversedHead.next;
            reversedHead.next = cur;
            // 原链表辅助指针后移
            cur = next;
        }
        return reversedHead.next;
    }

    /**
     * 直接反转法
     * @param head 头结点
     * @return 翻转后的头结点
     */
    public static ListNode reverseList2(ListNode head) {
        // 校验合法性
        if (head == null) {
            return null;
        }
        // 定义三个指针
        // pre指针指向反转后的头结点
        ListNode pre = null;
        // cur指针指向未反转部分的头结点
        ListNode cur = head;
        // next指针指向未反转部分的头结点的下一个结点
        ListNode next = head.next;
        // 开始反转链表
        while (cur != null) {
            // 将当前结点连接到新链表上
            cur.next = pre;
            // pre指针持续指向新链表的头
            pre = cur;
            // 指针后移
            cur = next;
//            if (next.next != null) {
            // 上一句是错的，因为那样的话next指针没到null就停了，cur指针一直指向最后一个结点
            if (next != null) {
                next = next.next;
            }
        }
        return pre;
    }

    /**
     * 递归反转法
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        // 若当前结点或者下一个结点为空，直接返回当前结点
        if (head == null || head.next == null)
            return head;
        // 不断递归向后移动双指针直到标记到尾结点和倒数第二个结点
        ListNode tail = head.next;
        ListNode p = reverseList(head.next);
        // 依次取最后两个结点将其反转
        head.next = tail.next;
        tail.next = head;
        // 返回原链表的尾结点，也即反转后的链表的头结点，注意:每一层返回的p结点都是同一个结点
        return p;
    }
}
